package com.lsa.letcode.the64.minPathSum;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class Solution {
	public int minPathSum(int[][] grid) {
		if (grid.length == 1) {
			int sum = 0;
			for (int i = 0; i < grid[0].length; i++) {
				sum += grid[0][i];
			}
			return sum;
		}
		else if (grid[0].length == 1) {
			int sum = 0;
			for (int i = 0; i < grid.length; i++) {
				sum += grid[i][0];
			}
			return sum;
		}
		PriorityQueue<Cell> heap = new PriorityQueue<>(new Comparator2(), new Comparator<Cell>() {
			@Override
			public int compare(Cell o1, Cell o2) {
				int res = o1.X - o2.X;
				if (res == 0){
					res = o1.Y - o2.Y;
				}
				return res;
			}
		});
		heap.insert(new Cell(grid[0][0], 0, 0));

		Cell target = null;
		while (heap.size() > 0) {
			Cell min = heap.extractHead();

			boolean isNotRightmost = min.X < grid.length - 1;
			if (isNotRightmost) {
				int X = min.X + 1;
				Cell right = new Cell(min.dist + grid[X][min.Y], X, min.Y);
				putOrRelax(heap, min, right);
			}
			
			boolean isNotDownmost = min.Y < grid[0].length - 1;
			if (isNotDownmost) {
				int Y = min.Y + 1;
				Cell down = new Cell(min.dist + grid[min.X][Y], min.X, Y);
				putOrRelax(heap, min, down);
			}
			
			if (!isNotRightmost && !isNotDownmost) {
				target = min;
				break;
			}
		}
		
		Cell cell = target;
		int sum = 0;
		while(cell != null) {
			sum += grid[cell.X][cell.Y];
			cell = cell.parent;
		}

		heap.keyIndex.get(new Cell(grid[0][0], 0, 0));
		
		return sum;
	}

	private void putOrRelax(PriorityQueue<Cell> heap, Cell parent, Cell cell) {
		cell.parent = parent;
		if (!heap.updateKey(cell)) {
			heap.insert(cell);
		}
	}

	private static class Comparator2 implements Comparator<Cell> {
		@Override
		public int compare(Cell c1, Cell c2) {
			return c2.dist - c1.dist;
		}
	}

	static class Cell {
		int dist;
		int X;
		int Y;
		Cell parent;
		
		public Cell(int dist, int x, int y) {
			this.dist = dist;
			X = x;
			Y = y;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + X;
			result = prime * result + Y;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			Cell other = (Cell) obj;
			if (X != other.X)
				return false;
			if (Y != other.Y)
				return false;
			return true;
		}
	}

	public class PriorityQueue<E> implements Iterable<E> {
		private static final int INITIAL_SIZE = 24;
		private final Comparator<E> comparator;

		private Object[] elements = new Object[INITIAL_SIZE];
		private final Map<E, Integer> keyIndex;
		private int size;

		public PriorityQueue(Comparator<E> comparator, Comparator<E> treeCompa) {
			this.comparator = comparator;
			keyIndex = new TreeMap<>(treeCompa);
		}

		public int size() {
			return size;
		}

		public E head() {
			return get(0);
		}

		public E extractHead() {
			E e = get(0);
			swap(0, size - 1);
			keyIndex.remove(elements[size - 1]);
			--size;
			heapify(0);
			return e;
		}

		public boolean updateKey(E newKey) {
			Integer index = keyIndex.get(newKey);
			if (index != null) {
				updateKey(index, newKey);
			}
			return index != null;
		}

		public void updateKey(int i, E newKey) {
			E key = get(i);
			if (comparator.compare(key, newKey) >= 0) {
				return;
			}
			elements[i] = newKey;
			promote(i);
		}

		public void insert(E newKey) {
			size++;
			ensureCapacity();
			elements[size - 1] = newKey;
			keyIndex.put(newKey, size - 1);
			promote(size - 1);
		}

		private void ensureCapacity() {
			if (size == elements.length) {
				Object[] newElements = new Object[elements.length * 2];
				for (int i = 0; i < elements.length; i++) {
					newElements[i] = elements[i];
				}
				elements = newElements;
			}
		}

		private void promote(int i) {
			while (i > 0 && comparator.compare(get(parentIdx(i)), get(i)) < 0) {
				swap(parentIdx(i), i);
				i = parentIdx(i);
			}
		}

		@SuppressWarnings("unchecked")
		public E get(int i) {
			checkIndex(i);
			return (E) elements[i];
		}

		private void checkIndex(int i) {
			if (i < 0 || i >= size) {
				throw new IndexOutOfBoundsException();
			}
		}

		private int parentIdx(int i) {
			return (i + 1) / 2 - 1;
		}

		private int leftIdx(int i) {
			return 2 * i + 1;
		}

		private int rightIdx(int i) {
			return 2 * i + 2;
		}

		private void heapify(int i) {
			int left = leftIdx(i);
			int right = rightIdx(i);

			int max = i;
			if (left <= size() - 1
					&& comparator.compare(get(max), get(left)) < 0) {
				max = left;
			}

			if (right <= size() - 1
					&& comparator.compare(get(max), get(right)) < 0) {
				max = right;
			}

			if (max != i) {
				swap(i, max);
				heapify(max);
			}
		}

		private void swap(int i, int j) {
			checkIndex(i);
			checkIndex(j);
			Object tmp = elements[i];
			elements[i] = elements[j];
			elements[j] = tmp;

			keyIndex.put((E)elements[i], i);
			keyIndex.put((E)elements[j], j);
		}

		@Override
		public Iterator<E> iterator() {
			return new Iterator<E>() {
				int i = 0;

				@Override
				public boolean hasNext() {
					return i < size();
				}

				@SuppressWarnings("unchecked")
				@Override
				public E next() {
					return (E) elements[i++];
				}

				@Override
				public void remove() {
					throw new UnsupportedOperationException();
				}
			};
		}
	}
}